This work concerns the development of an Algebraic Multilevel method forcomputing stationary vectors of Markov chains. We present an efficientBootstrap Algebraic Multilevel method for this task. In our proposed approach,we employ a multilevel eigensolver, with interpolation built using ideas basedon compatible relaxation, algebraic distances, and least squares fitting oftest vectors. Our adaptive variational strategy for computation of the statevector of a given Markov chain is then a combination of this multileveleigensolver and associated multilevel preconditioned GMRES iterations. We showthat the Bootstrap AMG eigensolver by itself can efficiently compute accurateapproximations to the state vector. An additional benefit of the Bootstrapapproach is that it yields an accurate interpolation operator for many othereigenmodes. This in turn allows for the use of the resulting AMG hierarchy toaccelerate the MLE steps using standard multigrid correction steps. Theproposed approach is applied to a range of test problems, involvingnon-symmetric stochastic M-matrices, showing promising results for all problemsconsidered.
展开▼
